Методические указания и задание на выполнение контрольной работы

Задание на контрольную работу

Контрольная работа содержит 2 задачи. Вариант для каждой выбирается из таблицы (см. табл. «Исходные данные») по двум последним цифрам пароля.

Задача 1

Провести анализ сети, структура которой представлена на рис. 1:

а) построить дерево всех возможных простых путей от узла коммутации УК_i ко всем другим узлам сети, используя графический способ. Номер узла i взять из таблицы 1 в соответствии с номером варианта задания;

б) выделить пути ранга r не более трех в дереве путей для заданной в таблице 1 пары узлов УК_i и УК_j;

в) найти структурную матрицу сети;

г) используя структурную матрицу, определить пути ранга r не более 3 от узла УК_i до узла УК_j матричным способом и сравнить полученный результат с результатом пункта б;

д) найти квазисечения между узлами УК_i и УК_j для множества путей ранга r ≤ 3.

Рис.1. Структура сети

Таблица 1. Исходные данные

Задача 2

Определить значение показателя структурной надежности для двух вариантов связи между узлами выделенной группой узлов на сети, представленной на рис. 2.

В первом варианте, для связи каждой пары узлов выделенной группы, используются по одному кратчайшему по рангу пути. Во втором варианте - по два пути, при этом ранг используемых путей не должен быть более двух (r ≤ 2).

В качестве показателя структурной надежности предлагается использовать математическое ожидание числа связей в сети M(X).

Необходимо сравнить результаты расчета и сделать вывод о целесообразности использования нескольких путей между узлами для повышения структурной надежности сети.

Рис.2. Структура сети, где K_i – коэффициент готовности линии связи сети.

Исходные данные для различных вариантов задания представлены в таблице 3.

Таблица 2. Исходные данные

Коэффициенты готовности коммутационных узлов сети равны 1, т.е. считаем, что узлы абсолютно надежны.

Если между вршинами граф существует несколько путей второго ранга, для расчета используем путь, проходящий через узел с меньшим номером.

Методические указания к контрольной работе

Структурная надежность сети

Общие методические указания

Перед решением задачи записываются ее условия и исходные данные для требуемого варианта. Решения должны быть снабжены краткими пояснениями. В конце работы приводятся список используемой литературы. Номер варианта определяется двумя последними цифрами пароля.

Методические указания к задаче 1

Вначале необходимо усвоить ряд терминов и определений, относящихся к теоретической модели сети. Сеть связи отображается в виде графа, вершины которого сопоставляются с узлами (узлами первичной или узлами коммутации вторичной сети), а ребра (ветви), соединяющие узлы, линиям связи первичной сети или пучкам каналов вторичной сети. В зависимости от свойств линий связи, ребра могут быть ориентированными (направленными) или неориентированными (ненаправленными). Как вершине, так и ребру может быть приписан вес или совокупность весов, характеризующих их свойства, например надежность, пропускная способность, длина линии связи и т.п.

Для передачи информации в сети от узла коммутации УК_i к УКj должен быть использован путь , который представляется упорядоченным набором ребер и узлов, входящих в данный путь. Рангом пути г() называется число составляющих его ребер графа (линий связи сети).

Путь может записываться перечнем ребер. При этом будем считать, что, если ребро в данном пути направлено от узла с меньшим индексом к узлу с большим индексом, то оно обозначается символами, например, . В противном случае - .

Сечением сети по отношению к узлам i и j называется минимальная совокупность ребер, которые нужно изъять из сети с тем, чтобы узлы УК_i к УК_j оказались в разных, не связанных между собой, частях сети.

Существуют различные методы отыскания путей в графе сети. Рассмотрим графический и матричный метод отыскания путей.

Графический метод является одним из наиболее простых и поддающихся машинизации способов построения дерева путей. Этот способ позволяет определить все простые пути от одного заданного узла ко всем остальным узлам сети и состоит из построения дерева путей и просотру по этому дереву каждого пути.

Дерево путей для заданного узлу i строится по графу сети с использованием следующего алгоритма:

1. Отмечаем узел i и выбираем смежные с данным узлом узлы графа сети.

2. Получаем узлы узлы первого яруса по отношению к узлу i.

3. Для образования узлов r-го яруса (r = 2, 3, …, h, где h – максимально допустимое число переприемных участков в пути):

а) поочередно рассматриваем узлы (r – 1)-го яруса;

б) для каждого узла k в (r – 1) –ом ярусе выбираем поочередно смежные узлы;

в) исключаем номера узлов, относительно которых были образованы подмножества узлов в предыдущих ярусах, связанных узлом k. Оставшиеся узлы соответствуют подмножеству узлов r-го яруса, образованного узлом k.

4. Построение дерева путей продолжается до заданного h-го яруса.

Имея дерево путей относительно узла i, легко проследить любой из возможных путей с заданным числом переприемных участков r (рангом пути) между фиксированным узлом i и произвольным узлом j. Для этой цели:

1. В r-ом ярусе дерева, образованного относительно узла i, находим заданный конечный узел j.

2. Выписываем номера узлов, относительно которых образованы подмножества, связанные с выбранным узлом j. Выписанные узлы принадлежат пути от узла i к узлу j.

Пример

В качестве примера построим дерево путей для узла 6 сети, представленной виде графа на рисунке 5.

Рис.5. Структура сети

Определим множество путей от узла 6 к другим узлам сети графическим методом. Выписываем исходный узел 6, который относится к нулевому ярусу. По графу сети определяем смежные с узлом 6 узлы – 1, 2, 4 и 5, которые образуют узлы первого яруса. Для узла 1 выбираем узлы 2 и 6. Так как узел 1 связан с узлом 6 нулевого яруса, то во втором ярусе записываем только узел 2. Для узла 2 в подмножество узлов второго яруса попадают узлы 3 и 5. Для узла 4 в подмножество узлов второго яруса попадает узлы 3. Для узла 5 в подмножество узлов второго яруса попадает узел 4. Аналогичным образом определяются подмножество узлов третьего и последующих ярусов. Узлы смежных ярусов связываются между собой соответствуюшими ребрами графа сети с учетом исключения путей с повторяющимися узлами в этих путях.

На рисунке 7 приведено дерево путей для узла 6.

Используя данное дерево путей, запишем пути не более третьего ранга от узла 6 до узла 5:

Рис.6. Дерево путей ранга r ≤ 3 для узла 6

Матричный метод основан на составлении структурной матрицы B, с последующим ее разложением. Матрица B – квадратная матрица, строки и столбцы которой сопоставлены узлам сети. Связь внутри узла отображается единицей (1). Если связи между узлами нет, то вхождение матрицы равно нулю (0).

Значения матрицы B рассматриваются как элементы булевой алгебры с двумя значениями: 1- соединение есть, 0 – соединения нет. Поэтому матрицу B преобразуют как булеву матрицу, применяя к ней аппарат булевой алгебры. При этом будем использовать следующие основные правила и законы булевой алгебры.

1) - закон поглащения;

2)

3)

4)

5) - закон поглащения.

В дальнейшем знак логического умножения ∩ будем опускать. Знак логического сложения соответствует параллельному существованию путей в сети между узлами сети. Знак логического умножения будем рассматривать как последовательное соединение элементов сети в том или ином пути.

Множество путей m_ij может быть найдено раскрытием минора структурной матрицы B, путем вычеркивания i-го столбца и j-ой строки в матрице В, и последующим разложением полученного определителя.

При вычислении определителей матриц учитываем следующее:

а) если в каждой строке (столбце) определителя есть хотя бы одна единица, то определитель равен 1;

б) если в определителе строка (или столбец) состоит из одних нулей, то определитель равен нулю;

в) если строка (столбец) содержит одну единицу, а остальные нули, то ее (его) можно вычеркнуть;

г) для определения номера строки на последующем шаге разложения определителя, необходимо выбрать любое ребро графа сети из строки определителя, соответствующей рассматриваемому узлу на данном шаге разложения определителя. Номер строки на следующем шаге разложения определяется номером узла, с которым выбранное ранее ребро связывает рассматриваемый узел графа сети.

Рассмотрим пример определения путей в сети от узла i до узла j матричным методом.

Пример

Определим совокупность путей от узла 6 до узла 5 матричным методом, используя структуру сети представленную на рисунке 5.

Структурная матрица B для рассматриваемого примера имеет вид:

Для определения множества путей m₆₅ из матрицы B вычеркнем столбец 6 и строку 5, поскольку узел 6 является исходящим, а узел 5 – входящим. Получаем определитель, представленный на рис. 7а. Обращаемся к строке 6 определителя (рис.7а), так как узел 6 является исходящим. Анализ строки 6 показывает, что узел 6 связан с узлами 1, 2, 4 и 5 соответственно ребрами . Поэтому разложение определителя 7а осуществим по указанным ребрам (). В полученных определителях (рис.7 б, в, г, д), обращаемся, соотвественно, к строке 1, строке 2 и строке 4. Определитель 7д равен 1, так как в каждой строке определителя имеется по одной единицы.

Далее проведем разложение определителей 7б, 7в и 7г по ненулевым членам соответственно 1-ой, 2-ой и 4 ой строкам. Определители 7ж, 7е равны нулю, так как в каждой строке и столбце указанных определителей имеются нули. Определитель 7и равен единице, так как в каждой строке определителя имеется по одной единицы. Разложение определителей 7е и 7к осуществим соотетственно по ненулевым членам 2-ой строки и 3-ей строки. Получаем определители 8л и 8м. После разложения определителя 7л получаем 0, а после разложения определителя 7м получаем 1. Окончательно получим выражение:

Таким образом, от узла 6 к узлу 5 могут быть использованы четыре простых пути:

Следовательно, множество путей ранга не более 3-его (r ≤ 3) от узла 6 к узлу 5, полученных как графическим, так и матричным методами, совпадают. Последовательность разложения структурной матрицы B при определении путей от узла 6 к узлу 5 представлена на рис. 7.

Рис.7. Определение путей от узла 6 до узла 5 матричным методом.

Для нахождения сечений (квазисечений, т.е. сечения, рассекающие пути до определенного ранга), следует заменить функцию m_ij на двойственную, заменив операции логического сложения (коньюнкции) на операции логического умножения (дизъюнкции) и наоборот. Затем произвести упрощение полученного выражения. Каждое слагаемое данного выражения и будет искомое сечение.

Пример

Определим множество квазисечений для множества путей r ≤ 3 от узла 6 до узла 5. Из рассмотренного выше примера имеем:

Заменим функцию m₆₅ на двойственную S₆₅ и, произведя операции умножения и сложения, получим слагаемые, определяющие квазисечения между узлами 6 и5.

Удаление ребер из графа сети, входящих в любое из полученных слагаемых, делает сеть несвязанной по отношению к узлам 6 и 5 при использовании путей ранга не более трех.

Методические указания к задаче 2

Структурная надежность и живучесть сетей

Основные понятия и определения

В соответствии с ГОСТ 27.002-89 под надежностью понимают свойство объекта сохранять во времени в установленных пределах значения всех параметров, характеризующих способность выполнять требуемые функции в заданных режимах и условиях применения, технического обслуживания, ремонтов, хранения и транспортировки (dependability, reliability). Объектами могут быть различные системы и их элементы, сооружения связи, узлы и линии связи сети, различные детали и приборы. Элемент системы – это объект, представляющий отдельную часть системы. Система представляет собой объект, состоящий из совокупности элементов, связанных между собой определенными отношениями и взаимодействующими таким образом, чтобы обеспечить выполнение системой некоторого набора функций. Основными признаками системы являются: структурированность, взаимосвязность составляющих ее частей, подчиненность всей системы определенной цели. Системы функционируют во времени и пространстве.

В зависимости от назначения объекта, выполняемых им функций и условий эксплуатации различают несколько свойств объекта, связанных с надежностью. К этим свойствам объекта относятся:

- безотказность - свойство непрерывно сохранять работоспособность в течение заданного промежутка времени в определенных условиях эксплуатации (failure-free operation);

- долговечность - свойство системы длительно сохранять работоспособность в определенных условиях, что количественно характеризуется промежутком вре мени использования системы от начала эксплуатации до момента технической или экономической нецелесообразности ее дальнейшего применения, с учетом перерывов для технического обслуживания и ремонта (durability, longevity);

- отказоустойчивость – свойство объекта сохранять работоспособность при наличии в его составе поврежденных элементов (fault-tolerance);

- ремонтопригодность - возможность выполнения ремонта и технического обслуживания объекта (maintainability);

- восстанавливаемость - возможность обнаружения отказов и восстановления работоспособности объекта после отказа (restorability);

- сохраняемость - свойство объекта сохранять свои свойства при транспртировке или длительном хранение (storability).

В настоящее время все большее и большее внимания уделяют безопасности объекта, понимая под этим его свойством обеспечивать охрану случайностей и различных внешних воздействий (security).

Объект, в частности электросвязи, может находиться в следующих состояниях: работоспособном, исправном, неработоспособном, неисправном.

Состояние объекта, при котором он способен выполнять заданные функции, сохраняя значения основных параметров в пределах, установленных нормативно-технической документацией (НТД), называют работоспособным, а состояние, в котором объект удовлетворяет указанным техническим требованиям, - его исправным состоянием. Понятие исправность шире, чем понятие работоспособность. Работоспособный объект, в отличие от исправного, удовлетворяет лишь тем требованиям НТД, которые обеспечивают нормальную работу объекта для выполнения заданных функций. Состояние объекта, при котором он не способен полностью или частично выполнять требуемое предназначение называют неработоспособным, а состояние, при котором хотя бы один из элементов объекта не соответствует требованиям НТД, называют неисправным состоянием. Объект может быть работоспособным, но неисправным. Например, при механическом повреждении стоек оборудования, выходе из строя элементов сигнализации, повреждении изоляции кабеля и т.п., средства связи могут обеспечивать передачу информации по сети, хотя некоторые из укзанных выше элементов оборудования находятся в неисправном состоянии.

Работоспособность или неработоспособность объекта в общем случае могут быть полными или неполными. Полностью работоспособный объект обеспечивает в определенных условиях максимальную эффективность его применения. Эффективность применение в этих же условиях частично работоспособного объекта меньше максимально возможной, но значение ее показателей при этом находятся в пределах установленных для такого функционирования, которое считается нормальным. Частично неработоспособный объект может функциионировать, но уровень его эффективности при этом ниже допустимого. Подобные ситуации возникают на сети электросвязи при отказах некоторых линий связи или узлов коммутации. Полностью неработоспособный объект не может быть использован по назначению. Состояние объекта, при котором невозможно его дальнейшее использование из-за нарушения требований безопасности или отклонения параметров от норм, установленных НТД, называется предельным состоянием. Признаки предельного стояния устанавливаются нормативно-технической документацией на данный объект. В связи со сказанным, важными являются понятия повреждение (damage) и отказа (fault, failure) объекта. Повреждение – это событие, заключающееся в нарушении исправности объекта при сохранении его работоспособности. Событие, заключающееся в нарушении работоспособности объекта, называют отказом. Различают следующие виды отказов:

- Внезапные отказы, которые возникают в результате резкого скачкообразного изменения основных параметров под воздействием многих случайных факторов. Например, обрыв кабеля связи.

- Постепенные отказы, которые характеризуются плавным ухудшением параметров в результате изнашивания и старения элементов.

- Явные отказы, которые обнаруживаются при внешнем осмотре или включении аппаратуры.

- Независимые отказы, возникновение которых не связано с предшествующими отказами других элементов.

- Полные отказы, приводящие к полному нарушению работоспособности системы (элементов).

- Устойчивые отказы, которые устраняются только в результате проведения ремонта.

- Временные отказы, которые могут самопроизвольно исчезать без вмешательства обслуживающего персонала. Временные отказы называют сбоями (inerruption).

В зависимости от причин возникновения, отказы могут быть условно разбиты на три группы:

1. Конструкционные – отказы, обусловленные нарушениями норм и правил проектирования, ошибками разработчика объекта и т.п.

2. Производственные - отказы, обусловленные нарушениям технологического процесса изготовления или монтажа объекта.

3. Эксплуатационные – отказы, возникающие в процессе эксплуатации объекта. Например, вследствие старения оборудования, нарушений правил эксплуатации или влияния непредусмотренных внешних воздействий.

Все объекты, рассматриваемые в теории надежности, делятся на восстанавливаемые и невосстанавливаемые. В восстанавливаемых объектах, после возникновения отказа (повреждения), происходит замена или ремонт отказавшего (пов-режденного) элемента. Невосстанавливаемый объект, в случае отказа, не подлежит или не поддается восстановлению по техническим либо экономическим соображениям. Невосстанавливаемый объект достигает предельного состояния при возникновении отказа или при достижении заранее установленного предельно допустимого значения срока службы или суммарной наработки, устанавливаемой из соображений безопасности эксплуатации в связи с необратимым снижением эффективности использования ниже допустимой или в связи с увеличением интенсивности отказов. Один и тот же объект в зависимости от особенностей или этапов эксплуатации может считаться восстанавливаемым или невосстанавливаемым. Например, аппаратура спутника связи на этапе хранения относится к восстанавливаемым, а во время полета в космосе - невосстанавливаемым.

Совокупность технических характеристик, количественным образом опреде-ляющих свойства объекта, характризующих его надежность, называются показателями надежности.

Для сетей связи, являющихся сложными многофункциональными системами, состоящими из элементов (узлов, линий связи, систем передачи и другого оборудования) разнородных по своим свойствам, показателям надежности, назначению, дате изготовления, сроку ввода в эксплуатацию и т. п., можно выделить два осно-вных аспекта надежности, которые условно можно назвать аппаратурным и структурным [3]. Под аппаратурным аспектом будем понимать проблему надежности аппаратуры, отдельных устройств и их элементов, входящих в состав узлов и линий связи сети. Структурный аспект отражает функционирование сети в целом в зависимости от работоспособности или отказов узлов (станций, пунктов) или линий (магистралей, пучков каналов сети), т. е. он связан с возможностью существования в сети путей доставки информации. При этом под структурой сети понимается совокупность пунктов (узлов, станций и т.п.) сети и соединяющих их линий или каналов связи, в их взаимном расположении и с характеристиками по надежности, передаче и распределению информации. Надежность в этом случае будем называть структурной надежностью сети связи.

Учитывая многофункциональность сети, в которой при n узлах может быть организовано до n(n—1) межузловых связей, да еще разного вида (телеграф, телефон, звуковое или телевизионное вещание, передача данных и т. п.), определить, что следует понимать под отказом сети, т. е. определить, когда сеть в целом перестает выполнять свои функции, практически невозможно. Поэтому под отказом сети иногда понимают потерю связности узлов, т.е. невозможность передачи информации между узлами сети. Однако этот показатель может быть принят только в некоторых частных случаях, так как он не учитывает важности отдельных связей. В других случаях структурную надежность сети характеризуют некоторой «средней» величиной коэффициента готовности связи или путей в сети для заданных пар узлов. Более правильно, по-видимому, характеризовать надежность сети матрицей, вектором или перечнем показателей надежности линий или каналов сети или же для каждой пары пунктов сети - показателями надежности кратчайших или допустимых путей или всех возможных путей. Наконец, надежность сети может характеризоваться функциями (графиками) вероятностей того, что сохранится определенная часть из общего числа линий, путей или линий связи.

В данных МУ будем относить понятие надежности к путям или совокупностям путей между заданной парой пунктов (узлов), т. е. рассмотривать надежность связи между этими пунктами, считая, что известны показатели надежности линий и узлов сети связи, входящих в рассматриваемые пути.

Для связи между двумя фиксированными узлами (пунктами) в сети могут использоваться все возможные пути или, выбранное по какому-либо признаку, множество путей. Каждый путь при этом включает различное оборудование сети (станционное оборудование, оборудование систем передачи, линейно-кабельные сооружения и т.п.), через которые он проходит.

Под показателем надежности пути (надежность пути) будем понимать вероятность того, что данный путь в произвольный момент времени находится в работоспособном состоянии, а это означает, что работоспособным должно быть все оборудование, входящие в этот путь.

Надежность связи (вероятность связности) будем оценивать вероятностью того, что работоспособным является хотя бы один путь из множества путей, которые могут быть использованы для связи заданного узла с другим узлом сети.

Отказом линии будем называть такое состояние, при котором каналы, образующие рассматриваемую линию, либо полностью вышли из строя, либо их параметры настолько ухудшились, что практически их нельзя использовать (например, из-за больших помех, искажений, снижения уровня на приемном конце и т. п.) для данного вида связи.

Надежность линии – например, вероятность ее безотказной работы — определяется, с одной стороны, аппаратурной надежностью ее элементов, а с другой, — механической исправностью линейных сооружений.

Основными причинами отказов линий связи являются различные механические повреждения, возникающие при проведении строительных работ (до 60—65%) или вследствие стихийных бедствий (молнии, разливы рек, оползни — до 10—15%). Реже они являются следствием дефектов монтажа или строительства этих линий (8—15%) или неаккуратной работы обслуживающего персонала (2—10%). Число и длительность таких повреждений в значительной степени зависят от типа и устройства линий, их географического положения, уровня организации эксплуатационной службы и длины линии связи.

Отказ узла — невозможность передачи через него информации с входящих кналов на исходящие. Такой отказ эквивалентен одновременному отказу всех линий связи, инцидентных (принадлежащих) этому узлу. Отказ происходит, как правило, в результате механических разрушений части или всего оборудования (в результате пожара, стихийного бедствия и т. п.). Отказ узла приводит к нарушению значительно большего числа путей, чем отказ линии. Однако вероятность отказа узла значит показатели значительно меньше вероятности отказа линии. Часто предполагают, что вероятность отказа узла равна 0, т.е. считают, что узлы абсолютно надежны.

На рисунке 15 представлены возможные причины отказа узлов или линий свя-зи, которые целесообразно учитывать при разработке сетей связи .

Рис.15. Возможные причины отказа узла или линии связи

С точки зрения надежности линии и узлы сети принадлежат к элементам с восстановлением. Исключение составляют некоторые объекты, в частности, искусственные спутники земли спутниковых систем радиосвязи. Процесс функционирования восстанавливаемого элемента можно представить как последовательность интервалов времени работоспособных состояний и времени восстановления, включающих отказы и восстановление элементов (рис.16) Интервал времени работоспособного состояния объекта от начала эксплуатации до первого отказа называют наработкой на отказ. Интервал времени восстановления включает время, которое затрачивается на поиск неисправности, на ремонт (замену неисправных элементов), включение и т.п. Таким образом, время восстановления представляет то время, которое необходимо для того, чтобы объект из состояния отказа привести в состояние выполнения требуемых функций, т.е. в работоспособное состояние.

- интервал работоспособного состояния объекта;
- интервал восстановления объекта.
Рис. 16. Интервалы работоспособности и восстановления

В первом приближении интервалы времени и можно считать взаимно независимыми случайными величинами, имеющими определенное распределение со средним временем работоспособного состояния - То и временем восстановления - Тв. Тогда:

- среднее время безотказной работы – То (среднее время наработка на отказ) рассчитывается по формуле: То =

- среднее время восстановления – Тв - по формуле: Тв = .

Под надежностью линии будем понимать вероятность нахождения линии в работоспособном состоянии в произвольный момент времени или математическое ожидание доли времени, в течение которого линия находится в исправном состоянии. Это определение эквивалентно понятию коэффициента готовности (availability function) – К_ij линии связи . Тогда: К_ij = То / (То + Тв), или К_ij = µ / (λ + µ), где λ = 1 / То, отк/час - интенсивность отказов объекта; µ = 1 / Тв, вост/час - интенсивность восстановления объекта.

Вероятность отказа линии b_ij определяется по формуле : Ко_ij = 1 – К_ij.

Аналогичным образом определяется коэффициент готовности i-ого узла связи К_i.

Одним из основных количественных критериев надежности элементов или система также является вероятность безотказной работы. Эта величина представляет вероятность того, что время от включения элемента (системы) до первого отказа больше некоторой величины t. Если обозначить через ξ случайный момент времени, когда происходит отказ после включения, то вероятность того, что эта случайная величина будет не меньше чем t и есть вероятность безотказной работы p(t): .

Если под структурной надежностью обычно понимают надежность сети в нор-мальных условиях ее функционирования, то для определения особенностей функ-ционирования сети в чрезвычайных ситуациях вводят понятие живучесть сети связи (survivalability).

Это свойство сети определяется, как возможность ее функционирования в фарсмажорных условиях (наводнения, землетрясения, умышленные повреждения средств связи и т.п.). Свойство живучести позволяет сложной системе, к которым относятся и сети связи, сохраняться в экстремальных для нее условиях, приспособиться к ним, изменяя поведение, структуру, зачастую и цель функционирования. В зависимости от класса систем, их сложности, степени организованности, а также от выбранного уровня анализа свойство живучести может оцениваться как надежность, отказоустойчивость, адаптивность и устойчивость. Понятия надежность и отказоустойчивость рассмотрены выше. Устойчивость - свойство объекта возвращаться в начальное состояние после окончания вешнего воздействия. Адаптивность – свойство объекта приспосабливаться к изменяемым условиям внутренней и внешней среды путем использования различных механизмов приспособления, которые заложены в объекте.

Модели сети связи

При исследовании структурной надежности можно рассматривать две модели сети: детерминированная сеть или сеть стохастическая (случайная) в зависимости от того, учитывается или игнорируется случайный характер внешних или внутренних воздействий на элементы моделируемой реальной сети связи.

Элементы детерминированной сети принимают абсолютно надёжными элементами или абсолютно ненадежными. В стохастической сети некоторые или все элементы (узлы или линии связи) обладают конечной надежностью pi (0< pi < 1), где pi вероятностный показатель надежности i- ого элемента сети. Теоретической основой для исследования сетей, как первого, так и второго типа, является теория графов, теория вероятностей, булева алгебра.

Теория графов позволяет разработать формальные приемы исследования стру-ктурной надежности сетей связи не зависимо от их сложности. Информацию, содержащую в графе, можно представить алгебраической матрицей для последующей автоматизации исследований на ЭВМ. Для исследования детерминированной сети в качестве математической модели можно использовать простой, конечный ориентированный или неориентированный или смешанный граф G = (A,B), где A – множество вершин графа, а B – множество ребер графа. Каждому ребру сопоставляется не более двух вершин, которые называются концевыми. При этом вершины графа поставлены в соответствие узлам сети связи, а ребры графа – линиям связи.

Для исследования стохастической сети в качестве математической модели используется простой, конечный ориентированный или неориентированный или смешанный взвешенный граф G'=(A,B,K). Как и в случае детерминированной сети, вершины графа поставлены в соответствие узлам сети связи, а ребры графа – линиям связи. Веса злементов графа (множество K) представляют собой пока-затели надежности элементов сети связи, например, коэффициенты готовности соотвествующих элементов сети (рис.17).

Рис. 17. Математические модели стохастической сети

Показатели структурной надежности сети связи

Одним из важнейших вопросов при решении задач анализа и синтеза сетей связи, с учетом структурной надежности и живучести, является выбор показате-лей или системы показателей. Используемые в настоящее время показатели, ис-пользуемые для оценки структурной надежности и живучести сети связи можно условно разбить на две группы:

- структурные показатели;

- вероятностные показатели.

При использовании первой группы показателей сеть связи рассматривается как детерминированная.

К структурным показателям относятся :

- связность сети;

- ранг (значимость) элемента.

Связность сети (графа) характеризует свойство сети обеспечивать взаимную достижимость любой пары узлов (вершин) друг друга для передачи информации. Сеть связана тогда и только тогда, когда любые два узла могут быть соединены путем (маршрутом).

В ряде случаев для оценки связности сети используется понятие сечение (разрез). В некоторых случаях рассматривают такие сечения, которые делят сеть (граф) на две связные подсети. Такие сечения называют простыми. Рангом сечения называют число входящих в него линий связи (ребер графа сети).

Значимость элемента позволяет оценить роль каждого элемента сети, узла или линии связи, в процессе функционирования сети, а также последствия, которые может вызвать отказ того или иного элемента сети. Для определения значимости элементов сети используют оценки, получившие название коэффициентов влияния. При исследовании структурной надежности (живучести) сети, коэффициент влияния узла или линии связи определяется с учетом числа потерянных связей в сети при отказе данного элемента.

Пусть в сети при всех исправных линиях и узлах существует М связей между различными узлами сети. Отказ узла (линии связи) может привести к уменьше-нию числа связей в сети. Пусть М_i число связей, оставшихся в сети после удалеения i-ого элемента. Тогда коэффициент влияния i-ого элемента сети , можно оценить следующим образом:

где Mi - число связей, оставшихся в сети после отказа i-ого элемента.

При использовании второй группы показателей структурной надежности, сеть представляется в виде взвешенного графа (рис.17).

В качестве весов элементов графа сети (вершин или ребер) в этом случае, как уже указывалось, могут быть использованы, например, коэффициенты готовности элементов сети (узлов или линий связи сети). Как правило, предполагается, что элементы сети являются статистически независимыми (т.е. состояния элементов сети не зависят друг от друга) и могут находиться в работоспособном или неработоспособном состоянии. Предположение о статистической независимости элементов сети существенно упрощает расчет показателей структурной надежности. Кроме того, для оценки максимальной структурной надежности сети, часто предполагается, что узлы и линии связи сети обладают неограниченной пропускной способностью.

К вероятностным показателям относятся: надежность пути, надежность связи, вероятность связности нескольких или всех узлов сети, математическое ожидание числа связей или компоненты связности в сети.

Для оценки структурной надежности стохастической сети, представленной в виде взвешенного графа или гиперсети, могут быть использованы следующие вероятностные показатели :

• надежность пути;

• надежность связи (вероятность связности двух узлов сети при использовании для связи узлов более одного пути);

• вероятность связности нескольких (n > 2) или всех узлов сети;

• математическое ожидание числа связей в сети;

• математическое ожидание компоненты сязности и т.п.

Под надежностью пути, связывающего узел i с узлом j, будем понимать вероятность одновременного исправного состояния всех линий и узлов, образующих этот путь.

Надежность связи или вероятность связности двух узлов при использовании для связи узлов более одного пути - это вероятность существования хотя бы од-ного пути в работоспособном состоянии из заданного множества путей, связыва-ющих указанную пару узлов.

Вероятность связности нескольких (n > 2) или всех узлов сети представляет собой вероятность того, что одновременно между указанными несколькими или всеми узлами сети существует одновременно связь.

Математическое ожидание числа связей в сети определяет среднее число связей в сети между различными узлами при фиксированной надежности элементов сети (узлов и линий связи).

Математическое ожидание компоненты связности – среднее число узлов, образующих единую подсеть, между которыми может быть установлена связь.

Для оценки структурной надежности и живучести сети связи могут быть использованы и другие показатели.

Определение вероятностных показателей структурной надежности

Рассмотрим задачу определения надежности связи (вероятность связности) между узлами сети аs и аt, если задано множество путей μ_st, которые могут быть использованы для связи указанных узлов. В качестве математической модели сети используем вероятностный граф, веса вершин и ребер которого представляют показатели надежности (коэффициенты готовности или вероятность безотказной работы).

При использовании одного пути для связи двух вершин графа сети, надеж-ность связи вершин определяется следующим образом.

Пусть - конкретный путь (k-ый путь), связывающий вершину s с вершиной t. Надежность пути между вершинами s и t, при условии статистической независимости элементов графа сети, оценивается вероятностью одновременного исправного (работоспособного) состояния всех ребер графа (линий связи сети), образующих указанный путь, если вершины графа абсолютно надежны, т.е.

(1)

где - знак произведения;

p(b_ij) – вероятность исправного состояния ребра b_ij, принадлежащего пути между вершинами s и t;

для любого ребра, пренадлежащего пути ;

q(b_ij) -вероятность неисправного состояния ребра b_ij.

Если учитывать надежность вершин графа, то

(2)

где p(a_i) – показатель надежности a_i – ого узла, входящего в путь между узлами.

Надежность связи (вероятность связности) двух узлов s и t при использовании mst путей (k ≥ 2) -P_st,будем оценивать вероятностью исправного состояния хотя бы одного пути из заданного множества путей m_st. Если отдельные элементы пути (их участки или линии связи) образуют по отношению к узлам s и t параллельнопоследовательную структуру, то для определения надежности связи (вероятности связности) можно использовать общепринятые способы определения надежности структур с таким соединением элементов. При последовательном соединении можно пользоваться формулой (2.1, 2.2), а при параллельном соединении путей надежность связи рассчитывается по формуле

(3)

где m_st - совокупность параллельных путей, связывающих узлы s и t;

надежность k-ого пути из множества путей

Для определения надежности связи узла s с узлом t, при ограниченном числе используемых путей, предлагается следующий алгоритм:

1. По графу сети определим множество путей m_st, которые используются для связи узла s с узлом t. Например, используя графический метод.

2. Каждому пути поставим в соответствие случайное событие A_i, характеризующее исправное состояние i - ого пути.

3. Определим надежность каждого из указанных путей c учетом показателей надежности элементов сети, применяя формулу (1) или (2). Полученные выражения определяют вероятность наступления каждого события A_i.

4. Для определения надежности связи P_st узла s с узлом t, воспользуемся формулой для расчета вероятности суммы совместных событий A_i, поставленных в соответствие множеству путей между узлами s и t .

(4)

где m - число путей между узлом s и t;

A_i – событие, поставленное в соответствие исправному состоянию i-ого пути из множества путей m

P(А_i) – вероятность наступления события А_i;

P(А_i А_j) – вероятность совместного наступления двух событий А_i и А_j;

P(А_i А_j А_k) - вероятность совместного наступления трех событий А_i, А_j и А_k;

.

.

P (А₁ А₂ …А_m) – вероятность совместного наступления m событий А_i.

В соответствии с теоремой произведения вероятностей, вероятность произведения нескольких событий равна произведению вероятностей этих событий, причем вероятность каждого следующего по порядку события вычисляется при условии, что все предыдущие имели место. Тогда:

где условная вероятность наступления события А_j при условии, что произошло событие А_i.

Аналогично:

.

.

Пример 1

Определить надежность связи (вероятность связности) узла 1 с узлом 3 - Р₁₃ в сети, граф которой показан на рисунке 18. При этом для связи указанных узлов 1 и 3 используются пути: и . Элементы сети (узлы и линии связи) являются статистически независимыми. Показатели надежности элементов сети представляют их коэффициенты готовности.

Рис. 18. Граф сети

Для определения Р₁₃ воспользуемся выше приведенным алгоритмом расчета надежности связи. Поскольку пути заданы, реализацию алгоритма начнем со второго шага.

1. Поставим каждому из указанных путей случайные события А_i, соответствующие исправным состояниям этих путей.

2. Событие А₁ поставим в соответствие путь ;А₂ – ; А₃ – .

3. Определим вероятность наступления событий А_i, зная маршруты путей и коэффициенты готовности узлов и линий связи сети, а также, в качестве примера, вероятность совместного наступления событий А₁ и А₂ - P(А_i А_j).

где

Таким образом:

Аналогичным способом определяются вероятности совместного наступления других событий - P(А₁ А₃), P(А₂ А₃) и P(А₁ А₂ А₃).

4. Используя формулу (4), определим надежность связи Р₁₃.

Если узлы абсолютно надежны, т.е. коэффициенты готовности узлов сети равны 1, то имеем:

Подставляя конкретные значения коэффициентов готовности К_ij, рассчитаем Р₁₃.

Если коэффициенты готовности для всех линий связи одинаковые и равны 0.9, получим

Р₁₃ = 0.97119.

Для определения математического ожидания числа связей в сети М(Х) воспользуемся основными положениями теории вероятности. Пусть случайная величина Х поставлена в соответствие общему числу межузловых связей в сети. При наличии n взаимодействующих друг с другом узлов, случайная величина X, в зависимости от надежности узлов или линий связи, будет изменяться в пределах от 0 до n(n – 1) (0 ≤ X ≤ n(n – 1)). Если каждой связи в сети поставить в соответствие случайную величину x_i, то случайная величина X может быть определена как:

(5)

где M – число рассматриваемых связей в сети.

Тогда

(6)

В соответствии с теоремой сложения математических ожиданий случайных велчин, имеем

(7)

Величина является дискретной случайной величиной, принимающей значение 1, если i-ая связь существует в сети, или 0, если i-ая связь отсутствует, т.е. данные события образуют полную группу. Пусть P_i – вероятность того, что случайная величина принимает значение равное 1. Тогда, в соответствии с выше сказанным, (1­P_i) – вероятность того, что случайная величина принимает значение равное 0. Тогда математическое ожидание случайной величины x_i будет равно

Следовательно

(8)

Вероятность P_i эквивалентна надежности связи (вероятности связности) узлов, образующих i-ую связь.

С учетом выше сказанного, для определения математического ожидания числа связей в сети М (Х) предлагается использовать следующий алгоритм:

1. Сформировать список корреспондирующих пар узлов сети.

2. Определить пути, которые могут быть использованы для связи каждой пары узлов сети из заданного списка.

3. Для каждой пары узлов, с учетом надежности элементов сети и используемых для связи путей, определим вероятность связности.

4. Произведем суммирование значений вероятностей связности различных пар узлов сети из заданного списка. В результате получим абсолютное значение математического ожидания числа связей в сети – М (Х).

Удобнее и нагляднее число связей в сети выразить в относительных единицах. В этом случае величина М(Х)отн. может быть рассчитана по формуле:

(9)

где – число связей в сети из заданного списка корреспондирующих пар узлов, при условии, что все элементы сети абсолютно надежны.

Пример 2

Определить математическое ожидание числа связей М (Х)отн. для сети, представленной на рисунке 19, при условии, что используются все возможные пути для связи узлов сети и коэффициент готовности каждой линии связи (вес ребра графа сети) равен К = 0,9. Узлы сети абсолютно надежны.

Рис. 19. Граф сети

Для решения задачи используем алгоритм расчета математического ожидания числа связей М(Х), приведенный выше

1. Используя графический метод, изложенный в МУ к задаче 1, определим список путей, связывающих узлы сети. Для связи i – го узла с j – ым могут быть исполь-зованы по два пути. Ранг путей в сети изменяется от 1 до 3.

2. Определим надежность каждого из указанных путей в общем виде с учетом коэффициентов готовности линий связи сети (весов ребер графа сети), используя формулу (1).

3. Определим вероятности связности для каждой пары вершин графа (узлов сети), используя выражение (4).

4. Определим выражение для расчета математического ожидания числа связей в сети - М(Х).

5.Определим максимальное число межузловых связей в сети при абсолютно надежных элементах.

где n – число узлов сети (вершин графа n = 4).

6. Подставив значение К_г = 0,9 в выражение для М(Х), полученное в пункте 4, и, используя формулу (9), определим М(Х)отн.